/*
 * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package javax.swing.tree;

import javax.swing.event.TreeModelEvent;
import java.awt.Rectangle;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.NoSuchElementException;
import java.util.Stack;
import java.util.Vector;

import sun.swing.SwingUtilities2;

/**
 * NOTE: This will become more open in a future release.
 * <p>
 * <strong>Warning:</strong>
 * Serialized objects of this class will not be compatible with
 * future Swing releases. The current serialization support is
 * appropriate for short term storage or RMI between applications running
 * the same version of Swing.  As of 1.4, support for long term storage
 * of all JavaBeans&trade;
 * has been added to the <code>java.beans</code> package.
 * Please see {@link java.beans.XMLEncoder}.
 *
 * @author Rob Davis
 * @author Ray Ryan
 * @author Scott Violet
 */

public class VariableHeightLayoutCache extends AbstractLayoutCache {

  /**
   * The array of nodes that are currently visible, in the order they
   * are displayed.
   */
  private Vector<Object> visibleNodes;

  /**
   * This is set to true if one of the entries has an invalid size.
   */
  private boolean updateNodeSizes;

  /**
   * The root node of the internal cache of nodes that have been shown.
   * If the treeModel is vending a network rather than a true tree,
   * there may be one cached node for each path to a modeled node.
   */
  private TreeStateNode root;

  /**
   * Used in getting sizes for nodes to avoid creating a new Rectangle
   * every time a size is needed.
   */
  private Rectangle boundsBuffer;

  /**
   * Maps from <code>TreePath</code> to a <code>TreeStateNode</code>.
   */
  private Hashtable<TreePath, TreeStateNode> treePathMapping;

  /**
   * A stack of stacks.
   */
  private Stack<Stack<TreePath>> tempStacks;


  public VariableHeightLayoutCache() {
    super();
    tempStacks = new Stack<Stack<TreePath>>();
    visibleNodes = new Vector<Object>();
    boundsBuffer = new Rectangle();
    treePathMapping = new Hashtable<TreePath, TreeStateNode>();
  }

  /**
   * Sets the <code>TreeModel</code> that will provide the data.
   *
   * @param newModel the <code>TreeModel</code> that is to provide the data
   * @beaninfo bound: true description: The TreeModel that will provide the data.
   */
  public void setModel(TreeModel newModel) {
    super.setModel(newModel);
    rebuild(false);
  }

  /**
   * Determines whether or not the root node from
   * the <code>TreeModel</code> is visible.
   *
   * @param rootVisible true if the root node of the tree is to be displayed
   * @beaninfo bound: true description: Whether or not the root node from the TreeModel is visible.
   * @see #rootVisible
   */
  public void setRootVisible(boolean rootVisible) {
    if (isRootVisible() != rootVisible && root != null) {
      if (rootVisible) {
        root.updatePreferredSize(0);
        visibleNodes.insertElementAt(root, 0);
      } else if (visibleNodes.size() > 0) {
        visibleNodes.removeElementAt(0);
        if (treeSelectionModel != null) {
          treeSelectionModel.removeSelectionPath
              (root.getTreePath());
        }
      }
      if (treeSelectionModel != null) {
        treeSelectionModel.resetRowSelection();
      }
      if (getRowCount() > 0) {
        getNode(0).setYOrigin(0);
      }
      updateYLocationsFrom(0);
      visibleNodesChanged();
    }
    super.setRootVisible(rootVisible);
  }

  /**
   * Sets the height of each cell.  If the specified value
   * is less than or equal to zero the current cell renderer is
   * queried for each row's height.
   *
   * @param rowHeight the height of each cell, in pixels
   * @beaninfo bound: true description: The height of each cell.
   */
  public void setRowHeight(int rowHeight) {
    if (rowHeight != getRowHeight()) {
      super.setRowHeight(rowHeight);
      invalidateSizes();
      this.visibleNodesChanged();
    }
  }

  /**
   * Sets the renderer that is responsible for drawing nodes in the tree.
   *
   * @param nd the renderer
   */
  public void setNodeDimensions(NodeDimensions nd) {
    super.setNodeDimensions(nd);
    invalidateSizes();
    visibleNodesChanged();
  }

  /**
   * Marks the path <code>path</code> expanded state to
   * <code>isExpanded</code>.
   *
   * @param path the <code>TreePath</code> of interest
   * @param isExpanded true if the path should be expanded, otherwise false
   */
  public void setExpandedState(TreePath path, boolean isExpanded) {
    if (path != null) {
      if (isExpanded) {
        ensurePathIsExpanded(path, true);
      } else {
        TreeStateNode node = getNodeForPath(path, false, true);

        if (node != null) {
          node.makeVisible();
          node.collapse();
        }
      }
    }
  }

  /**
   * Returns true if the path is expanded, and visible.
   *
   * @return true if the path is expanded and visible, otherwise false
   */
  public boolean getExpandedState(TreePath path) {
    TreeStateNode node = getNodeForPath(path, true, false);

    return (node != null) ? (node.isVisible() && node.isExpanded()) :
        false;
  }

  /**
   * Returns the <code>Rectangle</code> enclosing the label portion
   * into which the item identified by <code>path</code> will be drawn.
   *
   * @param path the path to be drawn
   * @param placeIn the bounds of the enclosing rectangle
   * @return the bounds of the enclosing rectangle or <code>null</code> if the node could not be
   * ascertained
   */
  public Rectangle getBounds(TreePath path, Rectangle placeIn) {
    TreeStateNode node = getNodeForPath(path, true, false);

    if (node != null) {
      if (updateNodeSizes) {
        updateNodeSizes(false);
      }
      return node.getNodeBounds(placeIn);
    }
    return null;
  }

  /**
   * Returns the path for <code>row</code>.  If <code>row</code>
   * is not visible, <code>null</code> is returned.
   *
   * @param row the location of interest
   * @return the path for <code>row</code>, or <code>null</code> if <code>row</code> is not visible
   */
  public TreePath getPathForRow(int row) {
    if (row >= 0 && row < getRowCount()) {
      return getNode(row).getTreePath();
    }
    return null;
  }

  /**
   * Returns the row where the last item identified in path is visible.
   * Will return -1 if any of the elements in path are not
   * currently visible.
   *
   * @param path the <code>TreePath</code> of interest
   * @return the row where the last item in path is visible
   */
  public int getRowForPath(TreePath path) {
    if (path == null) {
      return -1;
    }

    TreeStateNode visNode = getNodeForPath(path, true, false);

    if (visNode != null) {
      return visNode.getRow();
    }
    return -1;
  }

  /**
   * Returns the number of visible rows.
   *
   * @return the number of visible rows
   */
  public int getRowCount() {
    return visibleNodes.size();
  }

  /**
   * Instructs the <code>LayoutCache</code> that the bounds for
   * <code>path</code> are invalid, and need to be updated.
   *
   * @param path the <code>TreePath</code> which is now invalid
   */
  public void invalidatePathBounds(TreePath path) {
    TreeStateNode node = getNodeForPath(path, true, false);

    if (node != null) {
      node.markSizeInvalid();
      if (node.isVisible()) {
        updateYLocationsFrom(node.getRow());
      }
    }
  }

  /**
   * Returns the preferred height.
   *
   * @return the preferred height
   */
  public int getPreferredHeight() {
    // Get the height
    int rowCount = getRowCount();

    if (rowCount > 0) {
      TreeStateNode node = getNode(rowCount - 1);

      return node.getYOrigin() + node.getPreferredHeight();
    }
    return 0;
  }

  /**
   * Returns the preferred width and height for the region in
   * <code>visibleRegion</code>.
   *
   * @param bounds the region being queried
   */
  public int getPreferredWidth(Rectangle bounds) {
    if (updateNodeSizes) {
      updateNodeSizes(false);
    }

    return getMaxNodeWidth();
  }

  /**
   * Returns the path to the node that is closest to x,y.  If
   * there is nothing currently visible this will return <code>null</code>,
   * otherwise it will always return a valid path.
   * If you need to test if the
   * returned object is exactly at x, y you should get the bounds for
   * the returned path and test x, y against that.
   *
   * @param x the x-coordinate
   * @param y the y-coordinate
   * @return the path to the node that is closest to x, y
   */
  public TreePath getPathClosestTo(int x, int y) {
    if (getRowCount() == 0) {
      return null;
    }

    if (updateNodeSizes) {
      updateNodeSizes(false);
    }

    int row = getRowContainingYLocation(y);

    return getNode(row).getTreePath();
  }

  /**
   * Returns an <code>Enumerator</code> that increments over the visible paths
   * starting at the passed in location. The ordering of the enumeration
   * is based on how the paths are displayed.
   *
   * @param path the location in the <code>TreePath</code> to start
   * @return an <code>Enumerator</code> that increments over the visible paths
   */
  public Enumeration<TreePath> getVisiblePathsFrom(TreePath path) {
    TreeStateNode node = getNodeForPath(path, true, false);

    if (node != null) {
      return new VisibleTreeStateNodeEnumeration(node);
    }
    return null;
  }

  /**
   * Returns the number of visible children for <code>path</code>.
   *
   * @return the number of visible children for <code>path</code>
   */
  public int getVisibleChildCount(TreePath path) {
    TreeStateNode node = getNodeForPath(path, true, false);

    return (node != null) ? node.getVisibleChildCount() : 0;
  }

  /**
   * Informs the <code>TreeState</code> that it needs to recalculate
   * all the sizes it is referencing.
   */
  public void invalidateSizes() {
    if (root != null) {
      root.deepMarkSizeInvalid();
    }
    if (!isFixedRowHeight() && visibleNodes.size() > 0) {
      updateNodeSizes(true);
    }
  }

  /**
   * Returns true if the value identified by <code>path</code> is
   * currently expanded.
   *
   * @return true if the value identified by <code>path</code> is currently expanded
   */
  public boolean isExpanded(TreePath path) {
    if (path != null) {
      TreeStateNode lastNode = getNodeForPath(path, true, false);

      return (lastNode != null && lastNode.isExpanded());
    }
    return false;
  }

  //
  // TreeModelListener methods
  //

  /**
   * Invoked after a node (or a set of siblings) has changed in some
   * way. The node(s) have not changed locations in the tree or
   * altered their children arrays, but other attributes have
   * changed and may affect presentation. Example: the name of a
   * file has changed, but it is in the same location in the file
   * system.
   *
   * <p><code>e.path</code> returns the path the parent of the
   * changed node(s).
   *
   * <p><code>e.childIndices</code> returns the index(es) of the
   * changed node(s).
   *
   * @param e the <code>TreeModelEvent</code> of interest
   */
  public void treeNodesChanged(TreeModelEvent e) {
    if (e != null) {
      int changedIndexs[];
      TreeStateNode changedNode;

      changedIndexs = e.getChildIndices();
      changedNode = getNodeForPath(SwingUtilities2.getTreePath(e, getModel()), false, false);
      if (changedNode != null) {
        Object changedValue = changedNode.getValue();

                /* Update the size of the changed node, as well as all the
                   child indexs that are passed in. */
        changedNode.updatePreferredSize();
        if (changedNode.hasBeenExpanded() && changedIndexs != null) {
          int counter;
          TreeStateNode changedChildNode;

          for (counter = 0; counter < changedIndexs.length;
              counter++) {
            changedChildNode = (TreeStateNode) changedNode
                .getChildAt(changedIndexs[counter]);
                        /* Reset the user object. */
            changedChildNode.setUserObject
                (treeModel.getChild(changedValue,
                    changedIndexs[counter]));
            changedChildNode.updatePreferredSize();
          }
        } else if (changedNode == root) {
          // Null indicies for root indicates it changed.
          changedNode.updatePreferredSize();
        }
        if (!isFixedRowHeight()) {
          int aRow = changedNode.getRow();

          if (aRow != -1) {
            this.updateYLocationsFrom(aRow);
          }
        }
        this.visibleNodesChanged();
      }
    }
  }


  /**
   * Invoked after nodes have been inserted into the tree.
   *
   * <p><code>e.path</code> returns the parent of the new nodes.
   * <p><code>e.childIndices</code> returns the indices of the new nodes in
   * ascending order.
   *
   * @param e the <code>TreeModelEvent</code> of interest
   */
  public void treeNodesInserted(TreeModelEvent e) {
    if (e != null) {
      int changedIndexs[];
      TreeStateNode changedParentNode;

      changedIndexs = e.getChildIndices();
      changedParentNode = getNodeForPath(SwingUtilities2.getTreePath(e, getModel()), false, false);
            /* Only need to update the children if the node has been
               expanded once. */
      // PENDING(scott): make sure childIndexs is sorted!
      if (changedParentNode != null && changedIndexs != null &&
          changedIndexs.length > 0) {
        if (changedParentNode.hasBeenExpanded()) {
          boolean makeVisible;
          int counter;
          Object changedParent;
          TreeStateNode newNode;
          int oldChildCount = changedParentNode.
              getChildCount();

          changedParent = changedParentNode.getValue();
          makeVisible = ((changedParentNode == root &&
              !rootVisible) ||
              (changedParentNode.getRow() != -1 &&
                  changedParentNode.isExpanded()));
          for (counter = 0; counter < changedIndexs.length; counter++) {
            newNode = this.createNodeAt(changedParentNode,
                changedIndexs[counter]);
          }
          if (oldChildCount == 0) {
            // Update the size of the parent.
            changedParentNode.updatePreferredSize();
          }
          if (treeSelectionModel != null) {
            treeSelectionModel.resetRowSelection();
          }
                    /* Update the y origins from the index of the parent
                       to the end of the visible rows. */
          if (!isFixedRowHeight() && (makeVisible ||
              (oldChildCount == 0 &&
                  changedParentNode.isVisible()))) {
            if (changedParentNode == root) {
              this.updateYLocationsFrom(0);
            } else {
              this.updateYLocationsFrom(changedParentNode.
                  getRow());
            }
            this.visibleNodesChanged();
          } else if (makeVisible) {
            this.visibleNodesChanged();
          }
        } else if (treeModel.getChildCount(changedParentNode.getValue())
            - changedIndexs.length == 0) {
          changedParentNode.updatePreferredSize();
          if (!isFixedRowHeight() && changedParentNode.isVisible()) {
            updateYLocationsFrom(changedParentNode.getRow());
          }
        }
      }
    }
  }

  /**
   * Invoked after nodes have been removed from the tree.  Note that
   * if a subtree is removed from the tree, this method may only be
   * invoked once for the root of the removed subtree, not once for
   * each individual set of siblings removed.
   *
   * <p><code>e.path</code> returns the former parent of the deleted nodes.
   *
   * <p><code>e.childIndices</code> returns the indices the nodes had
   * before they were deleted in ascending order.
   *
   * @param e the <code>TreeModelEvent</code> of interest
   */
  public void treeNodesRemoved(TreeModelEvent e) {
    if (e != null) {
      int changedIndexs[];
      TreeStateNode changedParentNode;

      changedIndexs = e.getChildIndices();
      changedParentNode = getNodeForPath(SwingUtilities2.getTreePath(e, getModel()), false, false);
      // PENDING(scott): make sure that changedIndexs are sorted in
      // ascending order.
      if (changedParentNode != null && changedIndexs != null &&
          changedIndexs.length > 0) {
        if (changedParentNode.hasBeenExpanded()) {
          boolean makeInvisible;
          int counter;
          int removedRow;
          TreeStateNode removedNode;

          makeInvisible = ((changedParentNode == root &&
              !rootVisible) ||
              (changedParentNode.getRow() != -1 &&
                  changedParentNode.isExpanded()));
          for (counter = changedIndexs.length - 1; counter >= 0;
              counter--) {
            removedNode = (TreeStateNode) changedParentNode.
                getChildAt(changedIndexs[counter]);
            if (removedNode.isExpanded()) {
              removedNode.collapse(false);
            }

                        /* Let the selection model now. */
            if (makeInvisible) {
              removedRow = removedNode.getRow();
              if (removedRow != -1) {
                visibleNodes.removeElementAt(removedRow);
              }
            }
            changedParentNode.remove(changedIndexs[counter]);
          }
          if (changedParentNode.getChildCount() == 0) {
            // Update the size of the parent.
            changedParentNode.updatePreferredSize();
            if (changedParentNode.isExpanded() &&
                changedParentNode.isLeaf()) {
              // Node has become a leaf, collapse it.
              changedParentNode.collapse(false);
            }
          }
          if (treeSelectionModel != null) {
            treeSelectionModel.resetRowSelection();
          }
                    /* Update the y origins from the index of the parent
                       to the end of the visible rows. */
          if (!isFixedRowHeight() && (makeInvisible ||
              (changedParentNode.getChildCount() == 0 &&
                  changedParentNode.isVisible()))) {
            if (changedParentNode == root) {
                            /* It is possible for first row to have been
                               removed if the root isn't visible, in which
                               case ylocations will be off! */
              if (getRowCount() > 0) {
                getNode(0).setYOrigin(0);
              }
              updateYLocationsFrom(0);
            } else {
              updateYLocationsFrom(changedParentNode.getRow());
            }
            this.visibleNodesChanged();
          } else if (makeInvisible) {
            this.visibleNodesChanged();
          }
        } else if (treeModel.getChildCount(changedParentNode.getValue())
            == 0) {
          changedParentNode.updatePreferredSize();
          if (!isFixedRowHeight() && changedParentNode.isVisible()) {
            this.updateYLocationsFrom(changedParentNode.getRow());
          }
        }
      }
    }
  }

  /**
   * Invoked after the tree has drastically changed structure from a
   * given node down.  If the path returned by <code>e.getPath</code>
   * is of length one and the first element does not identify the
   * current root node the first element should become the new root
   * of the tree.
   *
   * <p><code>e.path</code> holds the path to the node.
   * <p><code>e.childIndices</code> returns <code>null</code>.
   *
   * @param e the <code>TreeModelEvent</code> of interest
   */
  public void treeStructureChanged(TreeModelEvent e) {
    if (e != null) {
      TreePath changedPath = SwingUtilities2.getTreePath(e, getModel());
      TreeStateNode changedNode;

      changedNode = getNodeForPath(changedPath, false, false);

      // Check if root has changed, either to a null root, or
      // to an entirely new root.
      if (changedNode == root ||
          (changedNode == null &&
              ((changedPath == null && treeModel != null &&
                  treeModel.getRoot() == null) ||
                  (changedPath != null && changedPath.getPathCount() == 1)))) {
        rebuild(true);
      } else if (changedNode != null) {
        int nodeIndex, oldRow;
        TreeStateNode newNode, parent;
        boolean wasExpanded, wasVisible;
        int newIndex;

        wasExpanded = changedNode.isExpanded();
        wasVisible = (changedNode.getRow() != -1);
                /* Remove the current node and recreate a new one. */
        parent = (TreeStateNode) changedNode.getParent();
        nodeIndex = parent.getIndex(changedNode);
        if (wasVisible && wasExpanded) {
          changedNode.collapse(false);
        }
        if (wasVisible) {
          visibleNodes.removeElement(changedNode);
        }
        changedNode.removeFromParent();
        createNodeAt(parent, nodeIndex);
        newNode = (TreeStateNode) parent.getChildAt(nodeIndex);
        if (wasVisible && wasExpanded) {
          newNode.expand(false);
        }
        newIndex = newNode.getRow();
        if (!isFixedRowHeight() && wasVisible) {
          if (newIndex == 0) {
            updateYLocationsFrom(newIndex);
          } else {
            updateYLocationsFrom(newIndex - 1);
          }
          this.visibleNodesChanged();
        } else if (wasVisible) {
          this.visibleNodesChanged();
        }
      }
    }
  }

  //
  // Local methods
  //

  private void visibleNodesChanged() {
  }

  /**
   * Adds a mapping for node.
   */
  private void addMapping(TreeStateNode node) {
    treePathMapping.put(node.getTreePath(), node);
  }

  /**
   * Removes the mapping for a previously added node.
   */
  private void removeMapping(TreeStateNode node) {
    treePathMapping.remove(node.getTreePath());
  }

  /**
   * Returns the node previously added for <code>path</code>. This may
   * return null, if you to create a node use getNodeForPath.
   */
  private TreeStateNode getMapping(TreePath path) {
    return treePathMapping.get(path);
  }

  /**
   * Retursn the bounds for row, <code>row</code> by reference in
   * <code>placeIn</code>. If <code>placeIn</code> is null a new
   * Rectangle will be created and returned.
   */
  private Rectangle getBounds(int row, Rectangle placeIn) {
    if (updateNodeSizes) {
      updateNodeSizes(false);
    }

    if (row >= 0 && row < getRowCount()) {
      return getNode(row).getNodeBounds(placeIn);
    }
    return null;
  }

  /**
   * Completely rebuild the tree, all expanded state, and node caches are
   * removed. All nodes are collapsed, except the root.
   */
  private void rebuild(boolean clearSelection) {
    Object rootObject;

    treePathMapping.clear();
    if (treeModel != null && (rootObject = treeModel.getRoot()) != null) {
      root = createNodeForValue(rootObject);
      root.path = new TreePath(rootObject);
      addMapping(root);
      root.updatePreferredSize(0);
      visibleNodes.removeAllElements();
      if (isRootVisible()) {
        visibleNodes.addElement(root);
      }
      if (!root.isExpanded()) {
        root.expand();
      } else {
        Enumeration cursor = root.children();
        while (cursor.hasMoreElements()) {
          visibleNodes.addElement(cursor.nextElement());
        }
        if (!isFixedRowHeight()) {
          updateYLocationsFrom(0);
        }
      }
    } else {
      visibleNodes.removeAllElements();
      root = null;
    }
    if (clearSelection && treeSelectionModel != null) {
      treeSelectionModel.clearSelection();
    }
    this.visibleNodesChanged();
  }

  /**
   * Creates a new node to represent the node at <I>childIndex</I> in
   * <I>parent</I>s children.  This should be called if the node doesn't
   * already exist and <I>parent</I> has been expanded at least once.
   * The newly created node will be made visible if <I>parent</I> is
   * currently expanded.  This does not update the position of any
   * cells, nor update the selection if it needs to be.  If succesful
   * in creating the new TreeStateNode, it is returned, otherwise
   * null is returned.
   */
  private TreeStateNode createNodeAt(TreeStateNode parent,
      int childIndex) {
    boolean isParentRoot;
    Object newValue;
    TreeStateNode newChildNode;

    newValue = treeModel.getChild(parent.getValue(), childIndex);
    newChildNode = createNodeForValue(newValue);
    parent.insert(newChildNode, childIndex);
    newChildNode.updatePreferredSize(-1);
    isParentRoot = (parent == root);
    if (newChildNode != null && parent.isExpanded() &&
        (parent.getRow() != -1 || isParentRoot)) {
      int newRow;

            /* Find the new row to insert this newly visible node at. */
      if (childIndex == 0) {
        if (isParentRoot && !isRootVisible()) {
          newRow = 0;
        } else {
          newRow = parent.getRow() + 1;
        }
      } else if (childIndex == parent.getChildCount()) {
        newRow = parent.getLastVisibleNode().getRow() + 1;
      } else {
        TreeStateNode previousNode;

        previousNode = (TreeStateNode) parent.
            getChildAt(childIndex - 1);
        newRow = previousNode.getLastVisibleNode().getRow() + 1;
      }
      visibleNodes.insertElementAt(newChildNode, newRow);
    }
    return newChildNode;
  }

  /**
   * Returns the TreeStateNode identified by path.  This mirrors
   * the behavior of getNodeForPath, but tries to take advantage of
   * path if it is an instance of AbstractTreePath.
   */
  private TreeStateNode getNodeForPath(TreePath path,
      boolean onlyIfVisible,
      boolean shouldCreate) {
    if (path != null) {
      TreeStateNode node;

      node = getMapping(path);
      if (node != null) {
        if (onlyIfVisible && !node.isVisible()) {
          return null;
        }
        return node;
      }

      // Check all the parent paths, until a match is found.
      Stack<TreePath> paths;

      if (tempStacks.size() == 0) {
        paths = new Stack<TreePath>();
      } else {
        paths = tempStacks.pop();
      }

      try {
        paths.push(path);
        path = path.getParentPath();
        node = null;
        while (path != null) {
          node = getMapping(path);
          if (node != null) {
            // Found a match, create entries for all paths in
            // paths.
            while (node != null && paths.size() > 0) {
              path = paths.pop();
              node.getLoadedChildren(shouldCreate);

              int childIndex = treeModel.
                  getIndexOfChild(node.getUserObject(),
                      path.getLastPathComponent());

              if (childIndex == -1 ||
                  childIndex >= node.getChildCount() ||
                  (onlyIfVisible && !node.isVisible())) {
                node = null;
              } else {
                node = (TreeStateNode) node.getChildAt
                    (childIndex);
              }
            }
            return node;
          }
          paths.push(path);
          path = path.getParentPath();
        }
      } finally {
        paths.removeAllElements();
        tempStacks.push(paths);
      }
      // If we get here it means they share a different root!
      // We could throw an exception...
    }
    return null;
  }

  /**
   * Updates the y locations of all of the visible nodes after
   * location.
   */
  private void updateYLocationsFrom(int location) {
    if (location >= 0 && location < getRowCount()) {
      int counter, maxCounter, newYOrigin;
      TreeStateNode aNode;

      aNode = getNode(location);
      newYOrigin = aNode.getYOrigin() + aNode.getPreferredHeight();
      for (counter = location + 1, maxCounter = visibleNodes.size();
          counter < maxCounter; counter++) {
        aNode = (TreeStateNode) visibleNodes.
            elementAt(counter);
        aNode.setYOrigin(newYOrigin);
        newYOrigin += aNode.getPreferredHeight();
      }
    }
  }

  /**
   * Resets the y origin of all the visible nodes as well as messaging
   * all the visible nodes to updatePreferredSize().  You should not
   * normally have to call this.  Expanding and contracting the nodes
   * automaticly adjusts the locations.
   * updateAll determines if updatePreferredSize() is call on all nodes
   * or just those that don't have a valid size.
   */
  private void updateNodeSizes(boolean updateAll) {
    int aY, counter, maxCounter;
    TreeStateNode node;

    updateNodeSizes = false;
    for (aY = counter = 0, maxCounter = visibleNodes.size();
        counter < maxCounter; counter++) {
      node = (TreeStateNode) visibleNodes.elementAt(counter);
      node.setYOrigin(aY);
      if (updateAll || !node.hasValidSize()) {
        node.updatePreferredSize(counter);
      }
      aY += node.getPreferredHeight();
    }
  }

  /**
   * Returns the index of the row containing location.  If there
   * are no rows, -1 is returned.  If location is beyond the last
   * row index, the last row index is returned.
   */
  private int getRowContainingYLocation(int location) {
    if (isFixedRowHeight()) {
      if (getRowCount() == 0) {
        return -1;
      }
      return Math.max(0, Math.min(getRowCount() - 1,
          location / getRowHeight()));
    }

    int max, maxY, mid, min, minY;
    TreeStateNode node;

    if ((max = getRowCount()) <= 0) {
      return -1;
    }
    mid = min = 0;
    while (min < max) {
      mid = (max - min) / 2 + min;
      node = (TreeStateNode) visibleNodes.elementAt(mid);
      minY = node.getYOrigin();
      maxY = minY + node.getPreferredHeight();
      if (location < minY) {
        max = mid - 1;
      } else if (location >= maxY) {
        min = mid + 1;
      } else {
        break;
      }
    }
    if (min == max) {
      mid = min;
      if (mid >= getRowCount()) {
        mid = getRowCount() - 1;
      }
    }
    return mid;
  }

  /**
   * Ensures that all the path components in path are expanded, accept
   * for the last component which will only be expanded if expandLast
   * is true.
   * Returns true if succesful in finding the path.
   */
  private void ensurePathIsExpanded(TreePath aPath, boolean expandLast) {
    if (aPath != null) {
      // Make sure the last entry isn't a leaf.
      if (treeModel.isLeaf(aPath.getLastPathComponent())) {
        aPath = aPath.getParentPath();
        expandLast = true;
      }
      if (aPath != null) {
        TreeStateNode lastNode = getNodeForPath(aPath, false,
            true);

        if (lastNode != null) {
          lastNode.makeVisible();
          if (expandLast) {
            lastNode.expand();
          }
        }
      }
    }
  }

  /**
   * Returns the AbstractTreeUI.VisibleNode displayed at the given row
   */
  private TreeStateNode getNode(int row) {
    return (TreeStateNode) visibleNodes.elementAt(row);
  }

  /**
   * Returns the maximum node width.
   */
  private int getMaxNodeWidth() {
    int maxWidth = 0;
    int nodeWidth;
    int counter;
    TreeStateNode node;

    for (counter = getRowCount() - 1; counter >= 0; counter--) {
      node = this.getNode(counter);
      nodeWidth = node.getPreferredWidth() + node.getXOrigin();
      if (nodeWidth > maxWidth) {
        maxWidth = nodeWidth;
      }
    }
    return maxWidth;
  }

  /**
   * Responsible for creating a TreeStateNode that will be used
   * to track display information about value.
   */
  private TreeStateNode createNodeForValue(Object value) {
    return new TreeStateNode(value);
  }


  /**
   * TreeStateNode is used to keep track of each of
   * the nodes that have been expanded. This will also cache the preferred
   * size of the value it represents.
   */
  private class TreeStateNode extends DefaultMutableTreeNode {

    /**
     * Preferred size needed to draw the user object.
     */
    protected int preferredWidth;
    protected int preferredHeight;

    /**
     * X location that the user object will be drawn at.
     */
    protected int xOrigin;

    /**
     * Y location that the user object will be drawn at.
     */
    protected int yOrigin;

    /**
     * Is this node currently expanded?
     */
    protected boolean expanded;

    /**
     * Has this node been expanded at least once?
     */
    protected boolean hasBeenExpanded;

    /**
     * Path of this node.
     */
    protected TreePath path;


    public TreeStateNode(Object value) {
      super(value);
    }

    //
    // Overriden DefaultMutableTreeNode methods
    //

    /**
     * Messaged when this node is added somewhere, resets the path
     * and adds a mapping from path to this node.
     */
    public void setParent(MutableTreeNode parent) {
      super.setParent(parent);
      if (parent != null) {
        path = ((TreeStateNode) parent).getTreePath().
            pathByAddingChild(getUserObject());
        addMapping(this);
      }
    }

    /**
     * Messaged when this node is removed from its parent, this messages
     * <code>removedFromMapping</code> to remove all the children.
     */
    public void remove(int childIndex) {
      TreeStateNode node = (TreeStateNode) getChildAt(childIndex);

      node.removeFromMapping();
      super.remove(childIndex);
    }

    /**
     * Messaged to set the user object. This resets the path.
     */
    public void setUserObject(Object o) {
      super.setUserObject(o);
      if (path != null) {
        TreeStateNode parent = (TreeStateNode) getParent();

        if (parent != null) {
          resetChildrenPaths(parent.getTreePath());
        } else {
          resetChildrenPaths(null);
        }
      }
    }

    /**
     * Returns the children of the receiver.
     * If the receiver is not currently expanded, this will return an
     * empty enumeration.
     */
    public Enumeration children() {
      if (!this.isExpanded()) {
        return DefaultMutableTreeNode.EMPTY_ENUMERATION;
      } else {
        return super.children();
      }
    }

    /**
     * Returns true if the receiver is a leaf.
     */
    public boolean isLeaf() {
      return getModel().isLeaf(this.getValue());
    }

    //
    // VariableHeightLayoutCache
    //

    /**
     * Returns the location and size of this node.
     */
    public Rectangle getNodeBounds(Rectangle placeIn) {
      if (placeIn == null) {
        placeIn = new Rectangle(getXOrigin(), getYOrigin(),
            getPreferredWidth(),
            getPreferredHeight());
      } else {
        placeIn.x = getXOrigin();
        placeIn.y = getYOrigin();
        placeIn.width = getPreferredWidth();
        placeIn.height = getPreferredHeight();
      }
      return placeIn;
    }

    /**
     * @return x location to draw node at.
     */
    public int getXOrigin() {
      if (!hasValidSize()) {
        updatePreferredSize(getRow());
      }
      return xOrigin;
    }

    /**
     * Returns the y origin the user object will be drawn at.
     */
    public int getYOrigin() {
      if (isFixedRowHeight()) {
        int aRow = getRow();

        if (aRow == -1) {
          return -1;
        }
        return getRowHeight() * aRow;
      }
      return yOrigin;
    }

    /**
     * Returns the preferred height of the receiver.
     */
    public int getPreferredHeight() {
      if (isFixedRowHeight()) {
        return getRowHeight();
      } else if (!hasValidSize()) {
        updatePreferredSize(getRow());
      }
      return preferredHeight;
    }

    /**
     * Returns the preferred width of the receiver.
     */
    public int getPreferredWidth() {
      if (!hasValidSize()) {
        updatePreferredSize(getRow());
      }
      return preferredWidth;
    }

    /**
     * Returns true if this node has a valid size.
     */
    public boolean hasValidSize() {
      return (preferredHeight != 0);
    }

    /**
     * Returns the row of the receiver.
     */
    public int getRow() {
      return visibleNodes.indexOf(this);
    }

    /**
     * Returns true if this node has been expanded at least once.
     */
    public boolean hasBeenExpanded() {
      return hasBeenExpanded;
    }

    /**
     * Returns true if the receiver has been expanded.
     */
    public boolean isExpanded() {
      return expanded;
    }

    /**
     * Returns the last visible node that is a child of this
     * instance.
     */
    public TreeStateNode getLastVisibleNode() {
      TreeStateNode node = this;

      while (node.isExpanded() && node.getChildCount() > 0) {
        node = (TreeStateNode) node.getLastChild();
      }
      return node;
    }

    /**
     * Returns true if the receiver is currently visible.
     */
    public boolean isVisible() {
      if (this == root) {
        return true;
      }

      TreeStateNode parent = (TreeStateNode) getParent();

      return (parent != null && parent.isExpanded() &&
          parent.isVisible());
    }

    /**
     * Returns the number of children this will have. If the children
     * have not yet been loaded, this messages the model.
     */
    public int getModelChildCount() {
      if (hasBeenExpanded) {
        return super.getChildCount();
      }
      return getModel().getChildCount(getValue());
    }

    /**
     * Returns the number of visible children, that is the number of
     * children that are expanded, or leafs.
     */
    public int getVisibleChildCount() {
      int childCount = 0;

      if (isExpanded()) {
        int maxCounter = getChildCount();

        childCount += maxCounter;
        for (int counter = 0; counter < maxCounter; counter++) {
          childCount += ((TreeStateNode) getChildAt(counter)).
              getVisibleChildCount();
        }
      }
      return childCount;
    }

    /**
     * Toggles the receiver between expanded and collapsed.
     */
    public void toggleExpanded() {
      if (isExpanded()) {
        collapse();
      } else {
        expand();
      }
    }

    /**
     * Makes the receiver visible, but invoking
     * <code>expandParentAndReceiver</code> on the superclass.
     */
    public void makeVisible() {
      TreeStateNode parent = (TreeStateNode) getParent();

      if (parent != null) {
        parent.expandParentAndReceiver();
      }
    }

    /**
     * Expands the receiver.
     */
    public void expand() {
      expand(true);
    }

    /**
     * Collapses the receiver.
     */
    public void collapse() {
      collapse(true);
    }

    /**
     * Returns the value the receiver is representing. This is a cover
     * for getUserObject.
     */
    public Object getValue() {
      return getUserObject();
    }

    /**
     * Returns a TreePath instance for this node.
     */
    public TreePath getTreePath() {
      return path;
    }

    //
    // Local methods
    //

    /**
     * Recreates the receivers path, and all its children's paths.
     */
    protected void resetChildrenPaths(TreePath parentPath) {
      removeMapping(this);
      if (parentPath == null) {
        path = new TreePath(getUserObject());
      } else {
        path = parentPath.pathByAddingChild(getUserObject());
      }
      addMapping(this);
      for (int counter = getChildCount() - 1; counter >= 0; counter--) {
        ((TreeStateNode) getChildAt(counter)).resetChildrenPaths(path);
      }
    }

    /**
     * Sets y origin the user object will be drawn at to
     * <I>newYOrigin</I>.
     */
    protected void setYOrigin(int newYOrigin) {
      yOrigin = newYOrigin;
    }

    /**
     * Shifts the y origin by <code>offset</code>.
     */
    protected void shiftYOriginBy(int offset) {
      yOrigin += offset;
    }

    /**
     * Updates the receivers preferredSize by invoking
     * <code>updatePreferredSize</code> with an argument of -1.
     */
    protected void updatePreferredSize() {
      updatePreferredSize(getRow());
    }

    /**
     * Updates the preferred size by asking the current renderer
     * for the Dimension needed to draw the user object this
     * instance represents.
     */
    protected void updatePreferredSize(int index) {
      Rectangle bounds = getNodeDimensions(this.getUserObject(),
          index, getLevel(),
          isExpanded(),
          boundsBuffer);

      if (bounds == null) {
        xOrigin = 0;
        preferredWidth = preferredHeight = 0;
        updateNodeSizes = true;
      } else if (bounds.height == 0) {
        xOrigin = 0;
        preferredWidth = preferredHeight = 0;
        updateNodeSizes = true;
      } else {
        xOrigin = bounds.x;
        preferredWidth = bounds.width;
        if (isFixedRowHeight()) {
          preferredHeight = getRowHeight();
        } else {
          preferredHeight = bounds.height;
        }
      }
    }

    /**
     * Marks the receivers size as invalid. Next time the size, location
     * is asked for it will be obtained.
     */
    protected void markSizeInvalid() {
      preferredHeight = 0;
    }

    /**
     * Marks the receivers size, and all its descendants sizes, as invalid.
     */
    protected void deepMarkSizeInvalid() {
      markSizeInvalid();
      for (int counter = getChildCount() - 1; counter >= 0; counter--) {
        ((TreeStateNode) getChildAt(counter)).deepMarkSizeInvalid();
      }
    }

    /**
     * Returns the children of the receiver. If the children haven't
     * been loaded from the model and
     * <code>createIfNeeded</code> is true, the children are first
     * loaded.
     */
    protected Enumeration getLoadedChildren(boolean createIfNeeded) {
      if (!createIfNeeded || hasBeenExpanded) {
        return super.children();
      }

      TreeStateNode newNode;
      Object realNode = getValue();
      TreeModel treeModel = getModel();
      int count = treeModel.getChildCount(realNode);

      hasBeenExpanded = true;

      int childRow = getRow();

      if (childRow == -1) {
        for (int i = 0; i < count; i++) {
          newNode = createNodeForValue
              (treeModel.getChild(realNode, i));
          this.add(newNode);
          newNode.updatePreferredSize(-1);
        }
      } else {
        childRow++;
        for (int i = 0; i < count; i++) {
          newNode = createNodeForValue
              (treeModel.getChild(realNode, i));
          this.add(newNode);
          newNode.updatePreferredSize(childRow++);
        }
      }
      return super.children();
    }

    /**
     * Messaged from expand and collapse. This is meant for subclassers
     * that may wish to do something interesting with this.
     */
    protected void didAdjustTree() {
    }

    /**
     * Invokes <code>expandParentAndReceiver</code> on the parent,
     * and expands the receiver.
     */
    protected void expandParentAndReceiver() {
      TreeStateNode parent = (TreeStateNode) getParent();

      if (parent != null) {
        parent.expandParentAndReceiver();
      }
      expand();
    }

    /**
     * Expands this node in the tree.  This will load the children
     * from the treeModel if this node has not previously been
     * expanded.  If <I>adjustTree</I> is true the tree and selection
     * are updated accordingly.
     */
    protected void expand(boolean adjustTree) {
      if (!isExpanded() && !isLeaf()) {
        boolean isFixed = isFixedRowHeight();
        int startHeight = getPreferredHeight();
        int originalRow = getRow();

        expanded = true;
        updatePreferredSize(originalRow);

        if (!hasBeenExpanded) {
          TreeStateNode newNode;
          Object realNode = getValue();
          TreeModel treeModel = getModel();
          int count = treeModel.getChildCount(realNode);

          hasBeenExpanded = true;
          if (originalRow == -1) {
            for (int i = 0; i < count; i++) {
              newNode = createNodeForValue(treeModel.getChild
                  (realNode, i));
              this.add(newNode);
              newNode.updatePreferredSize(-1);
            }
          } else {
            int offset = originalRow + 1;
            for (int i = 0; i < count; i++) {
              newNode = createNodeForValue(treeModel.getChild
                  (realNode, i));
              this.add(newNode);
              newNode.updatePreferredSize(offset);
            }
          }
        }

        int i = originalRow;
        Enumeration cursor = preorderEnumeration();
        cursor.nextElement(); // don't add me, I'm already in

        int newYOrigin;

        if (isFixed) {
          newYOrigin = 0;
        } else if (this == root && !isRootVisible()) {
          newYOrigin = 0;
        } else {
          newYOrigin = getYOrigin() + this.getPreferredHeight();
        }
        TreeStateNode aNode;
        if (!isFixed) {
          while (cursor.hasMoreElements()) {
            aNode = (TreeStateNode) cursor.nextElement();
            if (!updateNodeSizes && !aNode.hasValidSize()) {
              aNode.updatePreferredSize(i + 1);
            }
            aNode.setYOrigin(newYOrigin);
            newYOrigin += aNode.getPreferredHeight();
            visibleNodes.insertElementAt(aNode, ++i);
          }
        } else {
          while (cursor.hasMoreElements()) {
            aNode = (TreeStateNode) cursor.nextElement();
            visibleNodes.insertElementAt(aNode, ++i);
          }
        }

        if (adjustTree && (originalRow != i ||
            getPreferredHeight() != startHeight)) {
          // Adjust the Y origin of any nodes following this row.
          if (!isFixed && ++i < getRowCount()) {
            int counter;
            int heightDiff = newYOrigin -
                (getYOrigin() + getPreferredHeight()) +
                (getPreferredHeight() - startHeight);

            for (counter = visibleNodes.size() - 1; counter >= i;
                counter--) {
              ((TreeStateNode) visibleNodes.elementAt(counter)).
                  shiftYOriginBy(heightDiff);
            }
          }
          didAdjustTree();
          visibleNodesChanged();
        }

        // Update the rows in the selection
        if (treeSelectionModel != null) {
          treeSelectionModel.resetRowSelection();
        }
      }
    }

    /**
     * Collapses this node in the tree.  If <I>adjustTree</I> is
     * true the tree and selection are updated accordingly.
     */
    protected void collapse(boolean adjustTree) {
      if (isExpanded()) {
        Enumeration cursor = preorderEnumeration();
        cursor.nextElement(); // don't remove me, I'm still visible
        int rowsDeleted = 0;
        boolean isFixed = isFixedRowHeight();
        int lastYEnd;
        if (isFixed) {
          lastYEnd = 0;
        } else {
          lastYEnd = getPreferredHeight() + getYOrigin();
        }
        int startHeight = getPreferredHeight();
        int startYEnd = lastYEnd;
        int myRow = getRow();

        if (!isFixed) {
          while (cursor.hasMoreElements()) {
            TreeStateNode node = (TreeStateNode) cursor.
                nextElement();
            if (node.isVisible()) {
              rowsDeleted++;
              //visibleNodes.removeElement(node);
              lastYEnd = node.getYOrigin() +
                  node.getPreferredHeight();
            }
          }
        } else {
          while (cursor.hasMoreElements()) {
            TreeStateNode node = (TreeStateNode) cursor.
                nextElement();
            if (node.isVisible()) {
              rowsDeleted++;
              //visibleNodes.removeElement(node);
            }
          }
        }

        // Clean up the visible nodes.
        for (int counter = rowsDeleted + myRow; counter > myRow;
            counter--) {
          visibleNodes.removeElementAt(counter);
        }

        expanded = false;

        if (myRow == -1) {
          markSizeInvalid();
        } else if (adjustTree) {
          updatePreferredSize(myRow);
        }

        if (myRow != -1 && adjustTree &&
            (rowsDeleted > 0 || startHeight != getPreferredHeight())) {
          // Adjust the Y origin of any rows following this one.
          startYEnd += (getPreferredHeight() - startHeight);
          if (!isFixed && (myRow + 1) < getRowCount() &&
              startYEnd != lastYEnd) {
            int counter, maxCounter, shiftAmount;

            shiftAmount = startYEnd - lastYEnd;
            for (counter = myRow + 1, maxCounter =
                visibleNodes.size();
                counter < maxCounter; counter++) {
              ((TreeStateNode) visibleNodes.elementAt(counter))
                  .shiftYOriginBy(shiftAmount);
            }
          }
          didAdjustTree();
          visibleNodesChanged();
        }
        if (treeSelectionModel != null && rowsDeleted > 0 &&
            myRow != -1) {
          treeSelectionModel.resetRowSelection();
        }
      }
    }

    /**
     * Removes the receiver, and all its children, from the mapping
     * table.
     */
    protected void removeFromMapping() {
      if (path != null) {
        removeMapping(this);
        for (int counter = getChildCount() - 1; counter >= 0; counter--) {
          ((TreeStateNode) getChildAt(counter)).removeFromMapping();
        }
      }
    }
  } // End of VariableHeightLayoutCache.TreeStateNode


  /**
   * An enumerator to iterate through visible nodes.
   */
  private class VisibleTreeStateNodeEnumeration implements
      Enumeration<TreePath> {

    /**
     * Parent thats children are being enumerated.
     */
    protected TreeStateNode parent;
    /**
     * Index of next child. An index of -1 signifies parent should be
     * visibled next.
     */
    protected int nextIndex;
    /**
     * Number of children in parent.
     */
    protected int childCount;

    protected VisibleTreeStateNodeEnumeration(TreeStateNode node) {
      this(node, -1);
    }

    protected VisibleTreeStateNodeEnumeration(TreeStateNode parent,
        int startIndex) {
      this.parent = parent;
      this.nextIndex = startIndex;
      this.childCount = this.parent.getChildCount();
    }

    /**
     * @return true if more visible nodes.
     */
    public boolean hasMoreElements() {
      return (parent != null);
    }

    /**
     * @return next visible TreePath.
     */
    public TreePath nextElement() {
      if (!hasMoreElements()) {
        throw new NoSuchElementException("No more visible paths");
      }

      TreePath retObject;

      if (nextIndex == -1) {
        retObject = parent.getTreePath();
      } else {
        TreeStateNode node = (TreeStateNode) parent.
            getChildAt(nextIndex);

        retObject = node.getTreePath();
      }
      updateNextObject();
      return retObject;
    }

    /**
     * Determines the next object by invoking <code>updateNextIndex</code>
     * and if not succesful <code>findNextValidParent</code>.
     */
    protected void updateNextObject() {
      if (!updateNextIndex()) {
        findNextValidParent();
      }
    }

    /**
     * Finds the next valid parent, this should be called when nextIndex
     * is beyond the number of children of the current parent.
     */
    protected boolean findNextValidParent() {
      if (parent == root) {
        // mark as invalid!
        parent = null;
        return false;
      }
      while (parent != null) {
        TreeStateNode newParent = (TreeStateNode) parent.
            getParent();

        if (newParent != null) {
          nextIndex = newParent.getIndex(parent);
          parent = newParent;
          childCount = parent.getChildCount();
          if (updateNextIndex()) {
            return true;
          }
        } else {
          parent = null;
        }
      }
      return false;
    }

    /**
     * Updates <code>nextIndex</code> returning false if it is beyond
     * the number of children of parent.
     */
    protected boolean updateNextIndex() {
      // nextIndex == -1 identifies receiver, make sure is expanded
      // before descend.
      if (nextIndex == -1 && !parent.isExpanded()) {
        return false;
      }

      // Check that it can have kids
      if (childCount == 0) {
        return false;
      }
      // Make sure next index not beyond child count.
      else if (++nextIndex >= childCount) {
        return false;
      }

      TreeStateNode child = (TreeStateNode) parent.
          getChildAt(nextIndex);

      if (child != null && child.isExpanded()) {
        parent = child;
        nextIndex = -1;
        childCount = child.getChildCount();
      }
      return true;
    }
  } // VariableHeightLayoutCache.VisibleTreeStateNodeEnumeration
}
